%% Macelo Barros de Almeida
%% Domingo, 11 de janeiro de 1998
%% 16:02 - Um calor infernal

\section{Teorema No Free Lunch (NFL)}

Pesquisando na internet por assuntos como regulariza\c{c}\~{a}o e valida\c
c\~{a}o cruzada acabei me deparando com o teorema NFL \cite{WOLPERT0195}.
Consegui obter dois trabalhos relacionados \cite{GOUTTE0197,WOLPERT0196}. Um deles, um \textit{technical report} dos que parecem ser
os criadores da teoria, \'{e} relativamente claro. O assunto foi publicado
inclusive na \textit{Neural Computation,} mas aplicados \`{a} valida\c{c}\~{a}o
cruzada e por outros autores \cite{ZHU0196}. Vou resumir nas pr\'{o}ximas
linhas a id\'{e}ia b\'{a}sica da teoria que, na realidade, \'{e} um forte
incentivo para a utiliza\c{c}\~{a}o de regulariza\c{c}\~{a}o em praticamente tudo.
S\'{o} espero n\~{a}o estar falando de algo j\'{a} conhecido por voc\^{e}s.

\subsection{No Free Lunch}

A abordagem para explica\c{c}\~{a}o do NFL passa por uma simplifica\c{c}\~{a}o
(sem perda de generaliza\c{c}\~{a}o, afirmam os autores), que \'{e} trabalhar com
conjuntos finitos. Considere um conjunto de $m$ pontos $x$ e o seus valores
de custo $y$, pertencentes a conjuntos finitos $X$ e $Y$, representados por 
$(x,y)^m  \in ( X,Y)^m $.
Este conjunto \'{e} denominado $d_m$ e pode ser definido como a seguir 
(onde $i$ varia de 1 a $m$):

\begin{equation}
d_m\equiv \left\{ d_m^{}\left( i\right) \right\} \equiv \left\{ d_m^x\left(
i\right) ,d_m^y\left( i\right) \right\} 
\end{equation}

Considere tamb\'{e}m uma fun\c{c}\~{a}o de custo $f$ pertencente a um conjunto de
poss\'{\i}veis fun\c{c}\~{o}es de custo $F$, que associa os valores de $x$ e $y$%
. O que o NFL afirma \'{e} que ``\textit{todos os algoritmos que procuram por
um extremo da fun\c{c}\~{a}o de custo possuem o mesmo desempenho, para qualquer
medida de performace utilizada, quando se usa uma m\'{e}dia envolvendo 
as fun\c{c}\~{o}es de custo '' (Wolpert e Macready).}

Para isto, considere um vetor $\vec c$, de dimens\~{a}o igual ao n\'{u}mero de
elementos no conjunto $d_m^y$, onde a sua \textit{i}-\'{e}sima posi\c{c}\~{a}o
cont\'{e}m o n\'{u}mero de elementos no conjunto $d_m$ tendo custo $f_i$, ou
seja, $\vec c$ \'{e} um vetor de frequ\^{e}ncias
(histograma). Este vetor ser\'{a} utilizado como um crit\'{e}rio para compara\c
c\~{a}o de algoritmos de busca. 

Assim, deseja-se saber a probabilidade de ocorrer um determinado vetor $\vec
c$, dado uma fun\c{c}\~{a}o de custo $f$, $m$ pontos e um algoritmo de busca $a$%
. Matematicamente:

\begin{equation}
P\left( \vec c\mid f,m,a\right) 
\end{equation}

O que se afirma \'{e} que, sendo $F_1$ e $F_2$ dois conjuntos de fun\c{c}\~{o}es
de custo, $a_1$ e $a_2$ dois algoritmos de busca diferentes e tendo-se um
crit\'{e}rio de compara\c{c}\~{a}o baseado no somat\'{o}rio das probabilidades
condicionais sobre cada conjunto de fun\c{c}\~{o}es, os valores finais ser\~{a}o
iguais, ou seja:

\begin{equation}
\sum\limits_{f\in F_1}^{}P\left( \vec c\mid f,m,a_1\right)
=\sum\limits_{f\in F_2}^{}P\left( \vec c\mid f,m,a_2\right) 
\end{equation}

Mais genericamente, poderia-se utilizar $P\left( \Phi \left( \vec c\right)
\mid f,m,a\right) $, onde $\Phi \left( \vec c\right) $ \'{e} um crit\'{e}rio
qualquer para medida de desempenho, baseado em $\vec c$.

Um resultado bastante interessante est\'{a} relacionado com o conhecimento a
priori da fun\c{c}\~{a}o de custo utilizada. Para um caso onde n\~{a}o se tenha
conhecimento a priori, isto \'{e}, n\~{a}o se tem depend\^{e}ncia condicional de $f
$, pode-se escrever:

\begin{equation}
P\left( \vec c\mid m,a\right) =\sum\limits_{f\in F}^{}P\left( \vec c\mid
f,m,a\right) P\left( f\mid m,a\right) =\sum\limits_{f\in F}^{}P\left( \vec
c\mid f,m,a\right) P\left( f\right) 
\end{equation}

Outro resultado est\'{a} ligado ao fato do valor esperado para $\vec c$ ser o
mesmo para todos os algoritmos utilizados, ou matematicamente:

\begin{equation}
E\left( \vec c\mid f,m,a\right) =\sum\limits_{\vec c}^{}\vec cP\left( \vec
c\mid f,m,a\right) 
\end{equation}

Dessa forma, para que se tenha uma busca eficiente, \'{e} necess\'{a}rio que
haja um casamento entre o algoritmo e a fun\c{c}\~{a}o de custo, procurando
utilizar conhecimento a priori. Caso contr\'{a}rio, a busca estar\'{a} exibindo
apenas um comportamento m\'{e}dio. Nas palavras dos autores: ``\textit{%
Intuitivamente, o teorema NFL ilustra que mesmo que se conhe\c{c}a alguma
coisa sobre f (talvez especificado atrav\'{e}s de P(f) ) mas n\~{a}o se
incorpore este conhecimento em a, ent\~{a}o n\'{o}s n\~{a}o temos certeza de que a
ser\'{a} efetivo, estando simplesmente confiando em uma associa\c{c}\~{a}o
fortuita entre f e a. ''}


